package org.example.sword2offer.primary;


import java.util.Stack;

/**
 * @author: lynn
 * @Descript: 最长回文字符串
 * @Answer：  https://www.bilibili.com/video/BV1tZ4y1W7v1?from=search&seid=13763603429335765732
 * @date: 2021/7/5 17:20
 * @version: 1.0
 */
public class Q82_LongestEchoString {
    public static void main(String[] args) {
        Q82_LongestEchoString longestEchoString=new Q82_LongestEchoString();
        String s="xadeedayjdeffedjag"; //fixme 中心扩散法
        System.out.println(longestEchoString.getLongestPalindrome(s,3));
    }

    public  int getLongestPalindrome(String A, int n) {// fixme  最长回文字符串

        int max=0;
        int start=0; //fixme 容易漏
        for (int i = start; i <A.length() ; i++) {
            int tmp=Math.max(maxStrLengthHelp(A,i,i),maxStrLengthHelp(A,i,i+1));
            if (tmp>max){
                max=tmp;
                //fixme 在不考虑长度奇数偶数的情况，如何根据中间点和最大连续长度求最左边或者最右边下标
                start=i+1-(tmp+1)/2; //fixme 这个公式记下
            }
        }
        return A.substring(start,start+max).length();
    }
    //fixme 该方法获取l,r为中心(字符串长度奇数个l,r重叠，否则l,r不重叠),最长回文串的个数
    public  int maxStrLengthHelp(String s,int l,int r){
        while(l>=0&& r<s.length() && s.charAt(l)==s.charAt(r)){
            l--;
            r++;
        }
        return r-l-1;//fixme 此时已经跳出去了， xadeeday  此时l=x,r=y;
    }



}
